/**
 * 盛水最多的容器
 *
 * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
 *
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 返回容器可以储存的最大水量。
 *
 * 说明：你不能倾斜容器。
 */

/**
 * 1. 这题可以暴力解决, 直接把所有的可能性全部遍历一遍, 在求出其中的最大值,
 * 但很明显, 这种解法有一个很明显的问题, 就是时间复杂度太大了
 * 时间复杂度 : O(n^2)
 * 空间复杂度 : O(1)
 *
 * 2. 有没有方法可以优化上面的方法呢, 咱仔细观察,
 * 当我们遍历整个数组时, 是按照先固定第一个数, 在依次枚举后面的数进行遍历的, 这就导致了他们的高度可能变小,
 * 同时长度在变大, 我们就会焦虑了, 这咱还怎么玩 ?
 * 我们试着想如果是长度在逐渐变小的话不就正好满足了我们的需求了吗, 于是灵感迸发, 我们先从固定第一个数, 然后
 * 从后面开始枚举数, 这样一来长度不就在变小了吗, 因为我们所要求的是最大值, 所以我们就得到了一个单调性, 如果
 * 长度小于原来两个的最小值, 就可以直接舍去, 娃哈哈, 太聪明了, 掉头一想, 如果我们从后面可以舍去值, 那从前
 * 面开始是不是也能舍掉值呢, 一想, 果真可以, 所以就得到了最终版本, 直接固定收尾的值, 找其中最小的, 想里面
 * 进发 直到两个数相遇(代表已经全部遍历完成) 废话不多说, 直接上代码
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public int maxArea(int[] height) {

        int n = height.length;

        // 固定收尾两个数
        int left = 0, right = n - 1;

        // 细节 : 如果开始只有两个数, 那么当我们进入会直接减掉一个, 会导致, 最开始的数据没算上
        // 当然也可以在循环里面先计算在判断(太笨了, 当时只顾着敲敲了)
        // 记录一开始的数值
        int tmp = right * Math.min(height[left], height[right]);

        // 当两个数相遇时, 就已经遍历完所有的数
        while (left < right) {

            // 判断谁小, 谁向里面移动
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }

            // 更新最大值
            tmp = Math.max(tmp, Math.min(height[left],
                    height[right]) * (right - left));
        }

        return tmp;
    }


    // *********************************************
    // 代码顺序优化, 学着点
    public int maxArea2(int[] arr) {

        int n = arr.length;

        // 记录最大值
        int sum = 0;

        int left = 0, right = n - 1;

        while(left < right) {

            // 先更新
            int len = right - left;
            int high = Math.min(arr[left], arr[right]);
            sum = Math.max(sum, high * len);

            // 再判断
            if(arr[left] < arr[right]) left++;
            else right--;
        }

        return sum;
    }

}